package com.atguigu.search;

import com.atguigu.sort.ArrCreator;
import com.atguigu.sort.MergeSort;

import java.util.Arrays;

public class InsertValueSort {
    public static void main(String[] args) {
//        int[] arr= ArrCreator.createRandArr(30);
//        MergeSort.sort(arr,0,arr.length-1,new int[arr.length]);
//
//        System.out.println(Arrays.toString(arr));
        int[] arr={28, 180, 247, 279, 463, 483, 574, 596, 651, 709, 752, 1068, 1231, 1266, 1332, 1534, 1706, 1732, 1768, 1780, 1825, 1846, 1996, 2068, 2144, 2326, 2347, 2562, 2710, 2769};
        int search = search(arr, 0, arr.length - 1, 2068);
        System.out.println("resIndex="+search);


    }

    public static int searchCount=1;

    /**
     * 插值排序,
     * 个人认为可称之为: 线性分隔查找
     * 使用此排序的前置依据是: 在自然界中, 大多数的升序数组, 是以接近线性的结构排列的.
     * 因此按照线性数值搜索, 理论上应该会比二分查找, 更快找到匹配值的索引. 在数据量较多时, 更是如此.
     * @param arr
     * @param left
     * @param right
     * @param findVal
     * @return
     */
    public static int search(int[] arr,int left,int right,int findVal){
        System.out.println("递归次数:"+searchCount++);

        if(left>right||findVal<arr[0]||findVal>arr[arr.length-1]){
            return -1;
        }

        int emuIndex=left+(findVal-arr[left])*(right-left)/(arr[right]-arr[left]);
        int emuVal=arr[emuIndex];

        if(findVal>emuVal){
            return search(arr,emuIndex+1,right,findVal);
        }
        if(findVal<emuVal){
            return search(arr,left,emuIndex-1,findVal);
        }
        return emuIndex;


    }
}
